{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #使用最小花费爬楼梯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCostClimbingStairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使用最小花费爬楼梯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>数组的每个下标作为一个阶梯，第 <code>i</code> 个阶梯对应着一个非负数的体力花费值&nbsp;<code>cost[i]</code>（下标从 <code>0</code> 开始）。</p>\n",
    "\n",
    "<p>每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。</p>\n",
    "\n",
    "<p>请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cost = [10, 15, 20]\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>&nbsp;示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= cost.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= cost[i] &lt;= 999</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 746&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/min-cost-climbing-stairs/\">https://leetcode-cn.com/problems/min-cost-climbing-stairs/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [GzCJIP](https://leetcode.cn/problems/GzCJIP/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [GzCJIP](https://leetcode.cn/problems/GzCJIP/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0] * (len(cost) + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "        for i in range(2, len(cost) + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[len(cost)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        mem = [None] * len(cost)\n",
    "        return min(self.subcost(0, mem, cost), self.subcost(1, mem, cost))\n",
    "\n",
    "    # cost of path from i to last\n",
    "    def subcost(self, i, mem, cost) -> int:\n",
    "        n = len(cost)\n",
    "        if mem[i]:\n",
    "            return mem[i]\n",
    "        else:\n",
    "            if i >= n-2:\n",
    "                mem[i] = cost[i]\n",
    "                return mem[i]\n",
    "            else:\n",
    "                mem[i] = cost[i] + min(self.subcost(i+1, mem, cost), self.subcost(i+2, mem, cost))\n",
    "                return mem[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0] * (len(cost) + 1)\n",
    "        for i in range(2, len(cost)+ 1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0]*len(cost)\n",
    "        dp[0]=cost[0]\n",
    "        dp[1]=cost[1]\n",
    "\n",
    "        for i in range(2,len(cost)):\n",
    "            dp[i] = min(dp[i-1],dp[i-2])+cost[i]\n",
    "        # print(dp)\n",
    "        return min(dp[-1],dp[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        for i in range(2, len(cost) + 1):\n",
    "            p1, p2 = p2, min(p1 + cost[i - 2], p2 + cost[i - 1])\n",
    "        return p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        a = b = c = 0\n",
    "        if len(cost) <= 2: return min(cost)\n",
    "        for i in range(2, len(cost) + 1):\n",
    "            c = min(a + cost[i - 2], b + cost[i - 1])\n",
    "            a, b = b, c\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = dp[1] = 0\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "        return dp[n]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        q1,q2=0,0\n",
    "        n=len(cost)\n",
    "        for i in range(2,n+1):\n",
    "            now=min(q2+cost[i-1],q1+cost[i-2])\n",
    "            q1,q2=q2,now\n",
    "        return q2\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        if n < 3:\n",
    "            return min(cost)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(2 , n + 1):\n",
    "            dp[i] = min(dp[i-2] + cost[i-2] , dp[i-1] + cost[i-1])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp0 = cost[0]\n",
    "        dp1 = cost[1]\n",
    "        n = len(cost)\n",
    "        for i in range(2, n):\n",
    "            dp0, dp1 = dp1, min(dp0, dp1) + cost[i]\n",
    "        return min(dp0, dp1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * n\n",
    "        for i in range(2, n):\n",
    "            dp[i] = min(dp[i-2]+ cost[i-2], dp[i-1]+ cost[i-1]) \n",
    "        return min(dp[-2]+ cost[-2], dp[-1]+ cost[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        INF = 10 ** 9\n",
    "        dp = [INF] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "        for i in range (2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp=[0]*(len(cost)+1)\n",
    "        for i in range(2,len(cost)+1):\n",
    "            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[len(cost)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0] * (len(cost)+1)\n",
    "\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "\n",
    "        for i in range(2,len(cost)+1):\n",
    "            dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2])\n",
    "        \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0] * (len(cost)+1)\n",
    "        for i in range(2, len(cost)+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        cost.append(0)\n",
    "        n = len(cost)\n",
    "        if n == 2:\n",
    "            return min(cost[0], cost[1])\n",
    "        dp = [0] * n\n",
    "        for i in range(2, n):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [float(\"inf\")] * (len(cost)+1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "        for i in range(2,len(cost)+1):\n",
    "            dp[i] = min(dp[i-1] + cost[i-1],dp[i-2]+cost[i-2])\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        prev = curr = 0\n",
    "        for i in range(2, n + 1):\n",
    "            nxt = min(curr + cost[i - 1], prev + cost[i - 2])\n",
    "            prev, curr = curr, nxt\n",
    "        return curr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        dp=[0]*(n+1)\n",
    "        dp[0]=dp[1]=0\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        l = len(cost)\n",
    "        tmp_cost = [0]*(l+1)\n",
    "\n",
    "        for i in range(2, l+1):\n",
    "            tmp_cost[i] = min(tmp_cost[i-1] + cost[i-1], tmp_cost[i-2] + cost[i-2])\n",
    "        return tmp_cost[-1]\n",
    "\n",
    "\n",
    "\n",
    "        # 记忆化递归\n",
    "        # @cache\n",
    "        # def dp(i):\n",
    "        #     \"\"\"\n",
    "        #     到第i个阶梯的最小花费\n",
    "        #     \"\"\"\n",
    "        #     if i<=1:\n",
    "        #         return 0  # cost[i]\n",
    "            \n",
    "        #     return min(dp(i-1)+cost[i-1], dp(i-2)+cost[i-2])\n",
    "        #     # return min(dp(i-1), dp(i-2)) + cost[i]\n",
    "        \n",
    "        # l = len(cost)\n",
    "        # return dp(l)\n",
    "        # # return min(dp(l-1), dp(l-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        if len(cost)==0:\n",
    "            return 0\n",
    "        N = len(cost)\n",
    "        dp=[0]*(N+1)\n",
    "        for i in range(2,len(cost)+1):\n",
    "            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        '''\n",
    "        dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        '''\n",
    "        dp = [0 for i in range(len(cost)+1)]\n",
    "        for i in range(2,len(cost)+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[len(cost)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0 for i in range(len(cost))]\n",
    "        dp[0], dp[1] = cost[0], cost[1]\n",
    "        for i in range(2, len(cost)):\n",
    "            dp[i] = min(cost[i] + dp[i - 1], cost[i] + dp[i - 2])\n",
    "        return min(dp[-1], dp[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # dp[i]   爬到第i级阶梯的最小花费\n",
    "        # dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        # dp = [0, 0, 0, 0]\n",
    "\n",
    "        dp = [0] * (len(cost) + 1)\n",
    "\n",
    "        for i in range(2, len(dp)):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        if cost:\n",
    "            dp[0] = cost[0]\n",
    "            dp[1] = cost[1]\n",
    "            for i in range(2, n):\n",
    "                dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]\n",
    "        dp[-1] = min(dp[-3], dp[-2])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2])\n",
    "        return dp[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        #dp(i) = min(dp(i-1)+cost[i-1],dp(i-2)+cost[i-2])\n",
    "       \n",
    "        n = len(cost)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * n\n",
    "        dp[0] = dp[1] = 0\n",
    "        for i in range(2,n):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return min(dp[n - 1] + cost[n - 1], dp[n - 2] + cost[n - 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # dp[n] = min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])\n",
    "        # 它在过的时候把两种上来的方案都考虑过了才选择最小的\n",
    "        # 它dp[n]只和dp[n-1]和dp[n-2]有关。\n",
    "        \n",
    "        n = len(cost)\n",
    "        a,b = 0,0\n",
    "        i = 2\n",
    "        while i<=n:\n",
    "            a,b = b,min(a+cost[i-2],b+cost[i-1])\n",
    "            i+=1\n",
    "        return b\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # 定义dp[i]:表示到达下标为i的台阶的最小花费\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0 for i in range(len(cost)+1)]\n",
    "        for i in range(2, len(cost)+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # dp[n] = min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])\n",
    "        # 它在过的时候把两种上来的方案都考虑过了才选择最小的\n",
    "        # 它dp[n]只和dp[n-1]和dp[n-2]有关。\n",
    "        \n",
    "        n = len(cost)\n",
    "        a,b = 0,0\n",
    "        i = 2\n",
    "        while i<=n:\n",
    "            a,b = b,min(a+cost[i-2],b+cost[i-1])\n",
    "            i+=1\n",
    "        return b\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = (len(cost)+1) * [0]\n",
    "        for i in range(2,len(cost)+1):\n",
    "            dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])\n",
    "        return dp[len(cost)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        l = len(cost)+1\n",
    "        fx1,fx2,ans = 0,0,0\n",
    "        for i in range(2,l):\n",
    "            ans = min(fx1+cost[i-2],fx2+cost[i-1])\n",
    "            fx1,fx2 = fx2,ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0] * (len(cost) + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "        for i in range(2, len(cost) + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[len(cost)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        q1,q2=0,0\n",
    "        n=len(cost)\n",
    "        for i in range(2,n+1):\n",
    "            now=(min(q2+cost[i-1],q1+cost[i-2]))\n",
    "            q1,q2=q2,now\n",
    "        return q2\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        INF = 10 ** 9\n",
    "        dp = [INF for _ in range(n + 1)]\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0] * (len(cost)+1)\n",
    "        for i in range(2, len(cost)+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "        return dp [len(cost)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        \n",
    "        f1 = 0\n",
    "        f2 = 0\n",
    "        for i in range(2, n + 1):\n",
    "            f3 = min(cost[i - 2] + f1, cost[i - 1] + f2)\n",
    "            f1 = f2\n",
    "            f2 = f3\n",
    "        return f3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0,0]\n",
    "        for i in range(2,len(cost)+1):\n",
    "            dp.append(min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]))\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        res = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            res[i] = min(res[i -1] + cost[i - 1],res[i -2] + cost[i - 2])\n",
    "        return res[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        y = cost[0]\n",
    "        e = cost[1]\n",
    "        for i in range(2, len(cost), 2):\n",
    "            y = min(y, e) + cost[i]\n",
    "            if i + 1 < len(cost):\n",
    "                e = min(y, e) + cost[i+1]\n",
    "        return min(y, e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]\n",
    "        '''\n",
    "        if cost[0] < cost[1]:\n",
    "            step = 0\n",
    "        else:\n",
    "            step = 1\n",
    "        totalcost = cost[step]\n",
    "        while step < len(cost)-3:\n",
    "            if cost[step+1] < cost[step+2]:\n",
    "                step += 1\n",
    "            else:\n",
    "                step += 2\n",
    "            totalcost += cost[step]\n",
    "        return totalcost\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        a, b = 0, 0\n",
    "        for index in range(2, len(cost) + 1):\n",
    "            a, b = b, min(a + cost[index - 2], b + cost[index - 1])\n",
    "\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # n=len(cost)\n",
    "        # dp=[0]*(n+1)\n",
    "        # for i in range(2,n+1):\n",
    "        #     dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        # return dp[n]\n",
    "        n=len(cost)\n",
    "        prev=curr=0\n",
    "        for i in range(2,n+1):\n",
    "            nxt=min(curr+cost[i-1],prev+cost[i-2])\n",
    "            prev,curr=curr,nxt\n",
    "        return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # dp[n] = min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])\n",
    "        # 它在过的时候把两种上来的方案都考虑过了才选择最小的\n",
    "        # 它dp[n]只和dp[n-1]和dp[n-2]有关。\n",
    "        \n",
    "        n = len(cost)\n",
    "        a,b = 0,0\n",
    "        i = 2\n",
    "        while i<=n:\n",
    "            a,b = b,min(a+cost[i-2],b+cost[i-1])\n",
    "            i+=1\n",
    "        return b\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        dp = [0] * len(cost)\n",
    "        dp[0] = cost[0]\n",
    "        dp[1] = cost[1]\n",
    "        for i in range(2, len(cost)):\n",
    "            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]\n",
    "        return min(dp[-1], dp[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # f(n) = min(f(n-1)+cost[n-1], f(n-2)+cost(n-2))\n",
    "    # f[0] = 0\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        l = len(cost)\n",
    "        ans = [0 for _ in range(l)]\n",
    "        for i in range(2,l):\n",
    "            ans[i] = min(ans[i-1]+cost[i-1],ans[i-2]+cost[i-2])\n",
    "        return min(ans[l-1] + cost[l-1],ans[l-2] + cost[l-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        prev = curr = 0\n",
    "        for i in range(2, n + 1):\n",
    "            nxt = min(curr + cost[i - 1], prev + cost[i - 2])\n",
    "            prev, curr = curr, nxt\n",
    "        return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        mincost=[0,0]\n",
    "        for i in range(2,len(cost)+1):\n",
    "            mincost.append(min(mincost[i-1]+cost[i-1],mincost[i-2]+cost[i-2]))\n",
    "        return mincost[len(cost)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * n\n",
    "\n",
    "        dp[0] = cost[0]\n",
    "        dp[1] = cost[1]\n",
    "        for i in range(2, n):\n",
    "            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]\n",
    "        return min(dp[-1], dp[-2])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # dp[n] = min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])\n",
    "        # 它在过的时候把两种上来的方案都考虑过了才选择最小的\n",
    "        # 它dp[n]只和dp[n-1]和dp[n-2]有关。\n",
    "        \n",
    "        n = len(cost)\n",
    "        if n==2: return min(cost[0],cost[1])\n",
    "\n",
    "        i = 3\n",
    "        a,b = 0,min(cost[0],cost[1])\n",
    "        while i<=n:\n",
    "            a,b = b,min(a+cost[i-2],b+cost[i-1])\n",
    "            i+=1\n",
    "        return b\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        # min_cost[n] = min(min_cost[n-1] + cost[n-1], min_cost[n-2] + cost[n-2])\n",
    "\n",
    "        min_cost = {}\n",
    "        min_cost[0] = 0\n",
    "        min_cost[1] = 0\n",
    "\n",
    "        n = len(cost)\n",
    "        for i in range(2, n+1):\n",
    "            min_cost[i] = min(min_cost[i-1] + cost[i-1], min_cost[i-2] + cost[i-2])\n",
    "        \n",
    "        return min_cost[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        l = len(cost)\n",
    "        ans = [0 for _ in range(l)]\n",
    "        for i in range(2,l):\n",
    "            ans[i] = min(ans[i-1]+cost[i-1],ans[i-2]+cost[i-2])\n",
    "        return min(ans[l-1] + cost[l-1],ans[l-2] + cost[l-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        mincost=[0,0]\n",
    "        n=len(cost)\n",
    "        for i in range(2,n+1):\n",
    "            mincost.append(min(mincost[i-1]+cost[i-1],mincost[i-2]+cost[i-2]))\n",
    "        return mincost[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        if len(cost) < 2:\n",
    "            return 0\n",
    "        \n",
    "        n = len(cost)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        if n <= 1:\n",
    "            return \n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 0\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[1] = 0\n",
    "        dp[2] = min(cost[0], cost[1])\n",
    "        for i in range(3, n+1):\n",
    "            # cost1 = dp[i - 1] + min(cost[i - 1], cost[i])\n",
    "            # cost2 = dp[i - 2] + min(cost[i - 1], cost[i - 2] + cost[i])\n",
    "            # dp[i] = min(cost1, cost2)\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        cost.append(0)\n",
    "        n=len(cost)\n",
    "        dp=[float('inf')]*(n)\n",
    "        dp[0]=0\n",
    "        dp[1]=0\n",
    "        for i in range(2,n):\n",
    "            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "\n",
    "        n = len(cost)\n",
    "        cost.append(0)\n",
    "\n",
    "        curr, prev1, prev2 = 0, cost[1], cost[0]\n",
    "\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            curr = min(prev1, prev2) + cost[i]\n",
    "\n",
    "            prev2 = prev1\n",
    "            prev1 = curr\n",
    "\n",
    "        return curr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = 0\n",
    "        dp[1] = min(cost[0], cost[1])\n",
    "        for i in range(2, len(cost)):\n",
    "            cost1 = dp[i - 1] + min(cost[i - 1], cost[i])\n",
    "            cost2 = dp[i - 2] + min(cost[i - 1], cost[i - 2] + cost[i])\n",
    "            dp[i] = min(cost1, cost2)\n",
    "        return dp[n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "        self.len = len(cost)\n",
    "        dp = [0 for i in range(self.len)]\n",
    "        # dp[i]是从站在第i阶向上爬的最小成本\n",
    "        dp[0] = cost[0]\n",
    "        dp[1] = cost[1]\n",
    "        for i in range(2, self.len):\n",
    "            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]\n",
    "        return min(dp[self.len-1], dp[self.len-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost: List[int]) -> int:\n",
    "\n",
    "        n = len(cost)\n",
    "        dp = [0]*(n+1)\n",
    "\n",
    "        # dp[0] = cost[0]\n",
    "        # dp[1] = cost[1]\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])\n",
    "\n",
    "        print(dp)\n",
    "        return dp[n]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
